﻿//https://leetcode.cn/problems/generate-parentheses/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    string path;
    vector<string> ret;
    int m, left, right;
public:
    vector<string> generateParenthesis(int n)
    {
        m = n;
        dfs();
        return ret;
    }

    void dfs()
    {
        if (right == m)
        {
            ret.push_back(path);
            return;
        }

        if (left < m)
        {
            //添加左括号
            path.push_back('(');
            left++;
            dfs();
            //回溯
            path.pop_back();
            left--;
        }

        if (right < left)
        {
            //添加右括号
            path.push_back(')');
            right++;
            dfs();
            //回溯
            path.pop_back();
            right--;
        }
    }
};